package graph;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashSet;
import java.util.Set;

public class GraphDfsAndBfs {
    public static <T> void dfs(Node<T> node) {
        if (null == node) {
            return;
        }

        Deque<Node<T>> stack = new ArrayDeque<>();
        Set<Node<T>> nodes = new HashSet<>();
        stack.push(node);
        nodes.add(node);
        while (!stack.isEmpty()) {
            Node<T> top = stack.pop();
            for (Node<T> nextNode : top.nextNodes) {
                if (nodes.contains(nextNode)) {
                    continue;
                }
                stack.push(top);
                stack.push(nextNode);
                nodes.add(nextNode);
                System.out.println(nextNode.value);
                break;
            }
        }
    }

    public static <T> void dfsRecursion(Node<T> node, Set<Node<T>> nodes) {
        if (null == node) {
            return;
        }
        nodes.add(node);
        System.out.println(node.value);
        for (Node<T> nextNode : node.nextNodes) {
            if (nodes.contains(nextNode)) {
                continue;
            }
            nodes.add(nextNode);
            dfsRecursion(nextNode, nodes);
        }
    }

    public static <T> void bfs(Node<T> node) {
        if (null == node) {
            return;
        }

        Deque<Node<T>> queue = new ArrayDeque<>();
        Set<Node<T>> nodes = new HashSet<>();
        queue.offer(node);
        nodes.add(node);
        while (!queue.isEmpty()) {
            Node<T> top = queue.poll();
            System.out.println(top.value);
            for (Node<T> nextNode : top.nextNodes) {
                if (nodes.contains(nextNode)) {
                    continue;
                }
                queue.offer(nextNode);
                nodes.add(nextNode);
            }
        }
    }

}
